package com.zj.leetcode.medium.binarySearch;

import java.util.Arrays;

/**
 * @program: algorithm
 * @description: 在排序数组中查找元素的第一个和最后一个位置
 * 34 find-first-and-last-position-of-element-in-sorted-array
 * @author: Zhang Bo
 * @create: 2022-04-20 14:17:09
 **/
public class FindFirstAndLastPositionOfElementInSortedArray {
    public static void main(String[] args) {
//        int[] nums = {5, 7, 7, 8, 8, 10};
//        int target = 6;
        int[] nums = {5,5};
        int target = 5;
        Solution solution = new FindFirstAndLastPositionOfElementInSortedArray().new Solution();
        System.out.println(Arrays.toString(solution.searchRange(nums, target)));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 首先使用二分查找查找元素大概位置，
         * 然后左右扩展
         *
         * @param nums
         * @param target
         * @return
         */
        public int[] searchRange(int[] nums, int target) {

            if (nums == null || nums.length < 1) {
                return new int[]{-1, -1};
            }
            if (nums.length == 1) {
                return nums[0] ==target ? new int[]{0, 0} : new int[]{-1, -1};
            }
            int l = 0;
            int r = nums.length;
            int mid = (r - l) / 2 + l;

            int tempL = l;
            int tempR = r;
            while (nums[mid] != target && l <= r) {
                if (nums[mid] > target) {
                    r = mid;
                }
                if (nums[mid] < target) {
                    l = mid;
                }

                if (tempL == l && tempR == r) {
                    return new int[]{-1, -1};
                }
                tempL = l;
                tempR = r;
                mid = (r - l) / 2 + l;
            }

            if (nums[mid] != target) {
                return new int[]{-1, -1};
            }

            int retL = mid;
            int retR = mid;
            while (retL >= 0 && nums[retL] == target ) {
                retL--;
            }

            while (retR < nums.length && nums[retR] == target) {
                retR++;
            }
            return new int[]{retL + 1, retR - 1};

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}